package tree;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TreeProblem {
    static class TreeNode {
        int val;

        TreeNode left;

        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    //给定两棵树的根节点,编写函数看这两棵树是否完全相同
    //如果在结构上相同,并且节点具有相同的值
    //也是通过递归的思想,先递归判断左子树是否相等
    // 再递归判断右子树是否相等,有一个环节判断不同,就返回false
    //所有的递归都完成后,也没有找到不同的地方,返回true
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            //两个树都是空,直接认为是相等的
            return true;
        }
        if ((p == null && q != null) || (p != null && q == null)) {
            return false;
            //一个为空,一个不为空,说明不相同
        }
        //当两个树都不为空时,开始按递归思路来
        //先检查根节点的值是否相等
        if (p.val != q.val) {
            return false;
        }
        boolean isLeftSame = isSameTree(p.left, q.left);
        boolean isRightSame = isSameTree(p.right, q.right);
        return isLeftSame && isRightSame;
        //会不断的向下递归,直到递归到叶子节点,再一层层的向上返回
    }


    //给出两棵树的根节点,判断第二个树是不是第一棵树的子树,两棵树完全相同也算
    //同样是递归的思路,先判断两棵树是不是相同
    //如果不相同,再递归看第一棵树的左子树和右子树是否包含第二棵树
    public boolean isSubTree(TreeNode root, TreeNode subRoot) {
        //先判断为空的情况(大部分判断都是这样)
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null && subRoot != null) {
            return false;
        }
        if (root != null && subRoot == null) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        //如果两个树不相等就会继续向下走
        //如果两棵树不相同,就不断地进行递归判断,看左右子树是否包含
        return isSubTree(root.left, subRoot) || isSubTree(root.right, subRoot);
        //左右子树,只要有一个包含,就返回true,因为是或的表达式
    }

    //画图验证
    //翻转二叉树,递归的遍历二叉树,把每个节点的左右子树都进行交换
    public TreeNode inverseTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        //交换左右子树
        //此时要么是先递归,后交换,要么是先交换,后递归,不能按照中序遍历的方式进行
        inverseTree(root.left);
        inverseTree(root.right);

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        return root;
    }

    //    平衡二叉树,针对这个树的任意一个节点,左右子树高度差不超过1就认为是平衡的
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left == null && root.right == null) {
            return true;
        }//这个节点是叶子节点
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if (leftHeight - rightHeight > 1 || rightHeight - leftHeight > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }


    //给一个二叉树的根节点,判断它是否轴对称
    //即判定左右子树是否互为镜像
//    分以下三步
//    1.根节点的值是否相同,若不同,直接返回false
    //2.判断t1.left和t2.right是否互为镜像
    //3.判断t1.right和t2.left是否互为镜像


    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return true;
        }
        if ((t1 == null && t2 != null) || (t1 != null && t2 == null)) {
            return false;
        }
//        这里可以直接简写成下面这种,因为第一个if已经判断过了两个都为null的情况
//        但是这种写法没有第一种简单易懂
//        if(t1 == null || t2 == null){
//            return false;
//        }
        if (t1.val != t2.val) {
            return false;
        }
        boolean isMirror1 = isMirror(t1.left, t1.right);
        boolean isMirror2 = isMirror(t2.left, t2.right);
        return isMirror2 && isMirror1;
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);
    }

    //给出二叉树的根节点,对二叉树进行层序遍历,但这次输出的是一个二维数组的格式,相当于每层是一个一维的数组
    //[[3],[9,20],[15,7]],
    // 可以进行先序遍历,递归的时候,给递归的方法,加上辅助的参数,level表示当前层数
    //递归过程中,根据level的值,决定当前这个节点放到哪一层

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        //这个二维的List里面是没有任何行的
        if (root == null) {
            //注:这里返回的是一个空的List,而不是null
            return result;
        }

        //创建一个辅助方法进行递归

        leveOrderHelper(root, 0, result);
        return result;
    }


    // 注:在这个题目中,是通过二维List来表示结果的,List中的[0]元素表示的就是根节点,
    // 如果把根节点视为第0层,那么此下时标就跟节点的层数对应上了,比较容易计算
    //如果把根节点视为第一层,就需要把level - 1视为下标

    public void leveOrderHelper(TreeNode root, int level, List<List<Integer>> result) {
        if (root == null) {
            return;
        }
        //看当前level这一层的list是否被创建出来了
        if (result.size() == level) {
            //如果没有创建,就创建一下
            result.add(new ArrayList<>());
            //加上一个空行
            //因为层数是从0行开始的,而result.size()也是从0开始的,因此只要相等,就说明一维的List
            //还没有被创建
        }
        List<Integer> curRow = result.get(level);
        //取出二维List中的一维List
        curRow.add(root.val);
        //取出当前元素,添加到第level行
        //递归处理左右子树
        leveOrderHelper(root.left, level + 1, result);
        leveOrderHelper(root.right, level + 1, result);
    }

    //强度题
    //计算二叉树中两个点最近的公共祖先(每个点的公共祖先包括它们自己)
    //意味着公共祖先的子树中包含着p,q两个节点
    //意味着p,q可能存在于3个位置,
    //1.p/q是根节点
    //2.p/q存在于左子树
    //3.p/q存在于右子树
    //代码的整体思路:
    //从根节点出发,递归的针对每个子树,进行查找p和q的操作
    //对于任意一个节点,在根节点中查找p和q,在左子树中查找p和q,在右子树z中查找p和q
    //针对上述三个的查找范围,分别用int变量来表示查找结果,如果找到p或者q就认为返回值为1,如果没找到p或者
    //q就认为返回值是0

    private TreeNode lca = null;
    //在oj题中最好不要去创建成员变量,因为多组用例可能会使成员变量受到干扰,用的话,也一定要在方法前
    //对其进行初始化,以消除干扰
    //还有一种做法,要一次返回两个值,就是再创建一个类,
//    class Result{
//    int code;
//    Node lca;
//}
    public  TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        lca = null;
        if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        //这种情况是一个点是一个点的祖先,那最近的公共祖先一定是这个点
        //用一个辅助的方法进行递归
        find(root,p,q);
        return lca;
    }

    public int find(TreeNode root,TreeNode p,TreeNode q){
        if(root == null){
            return 0;
        }
        int mid = (root == p || root == q) ? 1:0;
        int left = find(root.left,p,q);
        int right = find(root.right,p,q);
        if(mid + right + left == 2){
            //说明root就是最近公共祖先
            //最近公共祖先只有一个,但是find方法是递归的过程中找到的
            //如何把这个公共祖先返回到lowestCommonAncestor中方法中呢
            //一个简单粗暴的做法,就是定义一个成员变量,用成员变量来接受最终效果
            lca = root;
        }
        //不是直接返回这三个变量的和
        //如果root中同时找到了p和q,此时root是公共祖先,这个时候还是算作1
        return mid + left + right > 0 ? 1:0;
        //结合图像来理解
    }

    //根据先序遍历和中序遍历结果来构造二叉树(给两个整数数组preorder和inorder)
    //构造二叉树并返回其根节点
    //思路:1.先序遍历时,第一个节点就是根节点
    //2.中序中,根节点的左侧就是左子树的中序,根节点的右侧就是右子树的中序
    //3.中序中,知道了哪些节点是左子树,哪些节点是右子树,此时先序中对应的序列,也就是左右子树先序的结果

    //通过index来表示当前取到了preorder中的哪个元素
    private int index = 0;

    public TreeNode buildTree(int []preorder,int [] inorder) {
        index = 0;
        return buildTreeHelper(preorder,inorder,0,inorder.length - 1);
    }

    public TreeNode buildTreeHelper(int [] preorder,int []inorder,int inLeft,int inRight){

        if(inLeft > inRight){
            return null;
        }
        //给定的中序区间是空区间,说明对应的是空树
        if(index >= preorder.length){
            //已经遍历完了preorder数组
            return null;
        }
        //取出index对应的元素,构造当前的根节点
        TreeNode root = new TreeNode(preorder[index]);
        index++;
        //接下来找到刚才root在中序中的位置
        int pos = findPos(inorder,inLeft,inRight,root.val);

        root.left = buildTreeHelper(preorder,inorder,inLeft,pos - 1);
        root.right = buildTreeHelper(preorder,inorder,pos + 1,inRight);
        return root;
    }

    public int findPos(int[] inOrder,int inLeft,int inRight,int val){
        //循环遍历即可
        for(int i = inLeft;i <= inRight;i++){
            if(inOrder[i] == val){
                return i;
            }
        }
        return -1;
    }

    //小结
    //对于二叉树的构建有两类题目
    //1. 通过带有空节点的先序来构建
    //2. 通过先序+中序的方式来构建

    //共同点:都是通过递归的方式来把每个节点构造出来,递归构造左子树,递归构造右子树
    //都是通过index,标记先序中访问到了哪个元素

    //差别:如何判断当前拿到的先序中的节点是父亲的左子树还是右子树
    //对于1来说,是通过递归遇到 # 来决定,优先往左子树填,左子树有 # 或  空格,就填到右子树

    //根据二叉树创建字符串,给出二叉树的根节点root,采用前序遍历的方式,将二叉树转为一个由括号和整数
    //组成的字符串,根(左子树)(右子树)
    //如果某个树的左子树不为空,右子树为空,需要补上空括号
    //如果左子树不为空,右子树为空,不需要加括号
    //如果左右子树都为空,也不需要加括号

    private StringBuilder result = new StringBuilder();

    public String tree2str(TreeNode root){
        //使用成员变量的时候,一定要注意多组用例的情况,每次都要把成员变量初始化,避免产生干扰
        result = new StringBuilder();
        if(root == null){
            return "";
        }
        tree2strHelper(root);
        result.deleteCharAt(0);
        result.deleteCharAt(result.length() - 1);
        return result.toString();
    }

    public void tree2strHelper(TreeNode root){
        if(root == null){
            return;
        }
        //访问当前的根节点,访问操作就是拼接字符串
        result.append("(");
        result.append(root.val);
        tree2strHelper(root.left);
        //在递归右子树之前,要判定是否左子树为空,如果左子树为空,并且右子树非空,再加上一组()
        if(root.left == null && root.right != null){
            result.append("()");
        }
        tree2strHelper(root.right);
        //修改递归子树的过程,结果也是在)里面
        result.append(")");
    }

    //不使用递归,进行二叉树的前序遍历,
    //理论上讲,所有的递归和循环代码,都是可以相互转换的,但是这样的转换可能会非常的复杂
    //递归的关键是"回溯"沿着调用的方向,返回到上一层
    //而此处就是手动构造栈,模拟回溯的过程
    //前序遍历是根,左,右
    //回溯发生在,左子树递归完毕后,需要回溯到根节点这一层,再递归访问右子树
    //此时就需要使用栈,模拟左子树递归完,再来递归访问右子树的过程,过程如下:
    //1.创建栈,根节点入栈
    //2.循环的把栈顶元素出栈,访问这个元素(题目中的访问,就是把元素加入到List中)
    //3.把右子树入栈,再把左子树入栈(栈是后进先出)
    //4.下次循环取出的栈顶就是左子树的根节点,访问,把这个根节点的左子树和右子树入栈
    //5.当所有左子树节点都访问完成,最后出栈才轮到刚才的根节点的右子树

    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        //注意这里的泛型参数是TreeNode,而不是Integer,后序要取出这里的左右子树
        //根节点入栈
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            result.add(cur.val);
            //针对右子树进行入栈
            if(cur.right != null){
                stack.push(cur.right);
            }
            //针对左子树入栈
            if(cur.left != null){
                stack.push(cur.left);
            }
        }
        return result;
    }

    //非递归实现中序遍历
    //中序的顺序是左,根,右
    //一上来不能直接访问根节点,要向左递归,必须得在左子树整个都完成了,才能访问根节点(栈顶的根节点),
    //添加到List,访问完栈顶元素,还不能出栈,得把栈顶元素的右子树再进行入栈
    //不能直接访问右子树的根节点,先入栈,再找右子树的左子树,一路入栈,一路找
    // 直到找到左子树为空,才能出栈访问
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(true){
            //一路向左找,只要遇到的节点不为空就入栈,此处无法访问根节点,必须找到最左侧节点
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //2.当上面的循环结束时,就意味着cur已经等于null了,栈定元素就是没有左子树的元素,就可以访问了
            if(stack.isEmpty()){
                break;
            }
            TreeNode top = stack.pop();
            result.add(top.val);
            //按照左根右这样的顺序,上面完成了根的访问,接下来从右子树开始继续1进行遍历
            cur = top.right;
        }
        return result;
    }

    //二叉树的非递归后序遍历
    //1,起手式和中序一样,一路往左走,遇到元素就入栈
    //2,当遇到null时,就可以出栈了,此时针对栈顶元素,能访问吗,不一定,需要判定
    //a)如果这个栈顶节点没有右子树,就直接访问
    //b)如果这个栈顶节点有右子树,就需要进一步的看右子树是否被访问过
    //如果右子树被访问过了,才能访问根节点
    //如果右子树没有被访问过,那就从右子树出发,继续上述过程
    //注:后序遍历结果,最后一个元素是根节点,倒数第二个元素是右子树的根节点
    //那回溯到根节点的时候,如何判断右子树有没有被访问过呢,可以取出结果List中的最后一个元素,
    // 看一下这个元素是不是当前根节点的右子树
    public List<Integer> postorderTraversal(TreeNode root){
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        //记录一个prev变量,表示上一个访问过的元素
        TreeNode prev = null;
        while(true){
            //先一路向左,把路径上的元素都入栈,后序遍历不能上来就访问根节点,而是要向左递归
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            if(stack.isEmpty()){
                break;
            }
            //当循环结束以后,取出栈顶元素,此时的栈顶元素能不能访问还不知道
            //先不着急pop,确定了能访问再pop
            TreeNode top = stack.peek();
            if(top.right == null||top.right == prev){
                //a)如果右子树为null,此时就可以访问这个根节点
                //b)如果右子树非空,但是已经访问过,此时也可以访问根节点
                result.add(top.val);
                stack.pop();
                //根节点这时就可以出栈了
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return result;
    }
}
